home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqdisplay / render.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  6.5 KB  |  224 lines
  1. #define    LIBQDISPLAY_CORE
  2. #include "../include/libqdisplay.h"
  3.  
  4. /*
  5.  *   "render" scenes by traversing over the
  6.  *   database, marking already-visited things,
  7.  *   using the PVS information and the "marksurface"
  8.  *   info; use one bsp routine to sort
  9.  */
  10.  
  11. unsigned char *visibleFaces;    //[MAX_MAP_FACES / 8 + 1];
  12. unsigned char *visibleLeafs;    //[MAX_MAP_LEAFS / 8 + 1];
  13. unsigned char *visibleNodes;    //[MAX_MAP_NODES];
  14.  
  15. int model = 0;
  16.  
  17. #if 0  // this works if IEEE and, sizeof(float) == sizeof(int)
  18. #define FLOAT_POSITIVE(x)   (*((int *)(&x)) >= 0)
  19. #else
  20. #define FLOAT_POSITIVE(x)   ((x) >= 0)
  21. #endif
  22.  
  23. static int bbox_inside_plane(short *mins, short *maxs, struct dplane_t * pl)
  24. {
  25.   short pt[3];
  26.  
  27.   // use quick test from graphics gems
  28.   if (FLOAT_POSITIVE(pl->normal[0]))
  29.     pt[0] = maxs[0];
  30.   else
  31.     pt[0] = mins[0];
  32.  
  33.   if (FLOAT_POSITIVE(pl->normal[1]))
  34.     pt[1] = maxs[1];
  35.   else
  36.     pt[1] = mins[1];
  37.  
  38.   if (FLOAT_POSITIVE(pl->normal[2]))
  39.     pt[2] = maxs[2];
  40.   else
  41.     pt[2] = mins[2];
  42.  
  43.  /*
  44.   * each frustum-plane in hesse-form have a positive and a negative half-space
  45.   * we can check if the distance between frustum-plane and point is positive or
  46.   * negative to check where the points is, in the positive or negative
  47.   * half-space
  48.   *
  49.   * if((DotProduct(frustumNormal, point) - frustumDistance) >= 0) -> if(DotProduct(frustumNormal, point) >= frustumDistance)
  50.   *  if is visible (lies in positive half-space)
  51.   * else
  52.   *  it is invisible (lies in negative half-space)
  53.   */
  54.   return DotProduct(pl->normal, pt) >= pl->dist;
  55. }
  56.  
  57. /*
  58.  * is the complete node between the frustum-planes?
  59.  */
  60. int node_in_frustrum(struct dnode_t * node)
  61. {
  62.   if (!bbox_inside_plane(node->mins, node->maxs, &planes[0])
  63.       || !bbox_inside_plane(node->mins, node->maxs, &planes[1])
  64.       || !bbox_inside_plane(node->mins, node->maxs, &planes[2])
  65.       || !bbox_inside_plane(node->mins, node->maxs, &planes[3]))
  66.     return 0;
  67.   return 1;
  68. }
  69.  
  70. /*
  71.  * is the complete leaf between the frustum-planes?
  72.  */
  73. int leaf_in_frustrum(struct dleaf_t * node)
  74. {
  75.   if (!bbox_inside_plane(node->mins, node->maxs, &planes[0])
  76.       || !bbox_inside_plane(node->mins, node->maxs, &planes[1])
  77.       || !bbox_inside_plane(node->mins, node->maxs, &planes[2])
  78.       || !bbox_inside_plane(node->mins, node->maxs, &planes[3]))
  79.     return 0;
  80.   return 1;
  81. }
  82.  
  83. /*
  84.  * mark all faces within a given leaf
  85.  */
  86. void mark_leaf_faces(__memBase, int leaf)
  87. {
  88.   int contents = bspMem->dleafs[leaf].contents;
  89.   short int i = bspMem->dleafs[leaf].nummarksurfaces;
  90.   unsigned short int *dms = &bspMem->dmarksurfaces[(int)(bspMem->dleafs[leaf].firstmarksurface + i)];
  91.  
  92.   for (--i; i >= 0; i--) {
  93.     int s = *--dms;
  94.     mark_face(s);
  95.   }
  96. }
  97.  
  98. /*
  99.  * The visibility lists are used by BSP Leaves, to
  100.  * determine which other leaves are visible from a given BSP Leaf.
  101.  * The Visibility list can be of size 0, in that case it will not be used.
  102.  * The game will crawl if there is no visibility list in a level.
  103.  *     u_char vislist[numvislist];    // RLE encoded bit array
  104.  * Basically, the visibility list is an array of bits. There is one such array
  105.  * of bits for each BSP Leaf.  They are all stored in the vislist array, and
  106.  * each leaf has an index to the first byte of it's own array
  107.  * The bit number N, if set to 1, tells that when laying in the tree leaf, one
  108.  * can see the leaf number N.
  109.  * The only complication is that this bit array in run-length encoded:
  110.  * when a set of bytes in the array are all zero, they are coded by zero
  111.  * followed by the number of bytes is the set (always more than 1).
  112.  * Normally, the size of the bit array associated to a leaf should be
  113.  * (numleafs+7)/8, but in fact due to the run length encoding, it's usually
  114.  * much less.
  115.  * When the player is in a leaf, the visibility list is used to tag
  116.  * all the leaves that can possibly be visible, and then only those
  117.  * leaves are rendered.
  118.  * Here is an example of decoding of visibility lists:
  119.  * // Suppose Leaf is the leaf the player is in.
  120.  *   v = Leaf.vislist;
  121.  *   for (L = 1; L < numleaves; v++)
  122.  *   {
  123.  *     if (visisz[v] == 0)           // value 0, leaves invisible
  124.  *     {
  125.  *       L += 8 * visisz[v + 1]    // skip some leaves
  126.  *       v++;
  127.  *     }
  128.  *     else                          // tag 8 leaves, if needed
  129.  *     {                           // examine bits right to left
  130.  *       for (bit = 1; bit != 0; bit = bit * 2, L++)
  131.  *       {
  132.  *         if (visisz[v] & bit)
  133.  *         TagLeafAsVisible(L);
  134.  *       }
  135.  *     }
  136.  *   }
  137.  * Lots of thanks to Tony Myles who fixed the  bit mask formula.
  138.  * There is no necessity to unpack the visibility list in memory,
  139.  * because the code to read them is fast enough.
  140.  */
  141. int visit_visible_leaves(__memBase)
  142. {
  143.   int n, i;
  144.   unsigned char *vis;
  145.  
  146.   n = find_leaf(bspMem);
  147.   
  148.   if (n == 0 || bspMem->dleafs[n].visofs < 0) {
  149.     memset(visibleLeafs, 0xFF, bspMem->dmodels[model].visleafs * sizeof(unsigned char));
  150.     return 0;
  151.   }
  152.   else {
  153.     memset(visibleLeafs, 0x00, bspMem->dmodels[model].visleafs * sizeof(unsigned char));
  154.   }
  155.  
  156.   vis = bspMem->dvisdata + bspMem->dleafs[n].visofs;
  157.   for (i = 1; i < bspMem->dmodels[model].visleafs;) {
  158.     unsigned char v = *vis++;
  159.   
  160.     if (v == 0) {
  161.       i += *vis++ << 3;            // * 8
  162.     }
  163.     else {
  164.       if (v & 1)
  165.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  166.       i++;
  167.       if (v & 2)
  168.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  169.       i++;
  170.       if (v & 4)
  171.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  172.       i++;
  173.       if (v & 8)
  174.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  175.       i++;
  176.       if (v & 16)
  177.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  178.       i++;
  179.       if (v & 32)
  180.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  181.       i++;
  182.       if (v & 64)
  183.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  184.       i++;
  185.       if (v & 128)
  186.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  187.       i++;
  188.     }
  189.   }
  190.   return 1;
  191. }
  192.  
  193. // during a bsp recursion, draw all of the faces
  194. // stored on this node which are visible (i.e. just
  195. // test their mark flag)
  196. void render_node_faces(__memBase, int node, int side)
  197. {
  198.   int i, n, f;
  199.  
  200.   n = bspMem->dnodes[node].numfaces;
  201.   f = bspMem->dnodes[node].firstface;
  202.  
  203.   for (i = 0; i < n; ++i) {
  204.     if (bspMem->dfaces[f].side == side)
  205.       if (is_marked_face(f))
  206.     draw_face(bspMem, f);
  207.     unmark_face(f);
  208.     ++f;
  209.   }
  210. }
  211.  
  212. void render_world(__memBase)
  213. {
  214.   compute_view_frustrum();
  215.   update_water();
  216.  
  217.   //for(model = 0; model < bspMem->nummodels; model++) {
  218.     visit_visible_leaves(bspMem);
  219.     bsp_find_visible_nodes(bspMem, (int)bspMem->dmodels[model].headnode[0]);
  220.     bsp_explore_node(bspMem, (int)bspMem->dmodels[model].headnode[0]);
  221.     bsp_render_node(bspMem, (int)bspMem->dmodels[model].headnode[0]);
  222.   //}
  223. }
  224.